package com.ita.dataset;

/**
 * headNode endNode
 * 
 */

public class DoubleLinkedList<T> {

	private Node<T> headNode;
	private Node<T> endNode;
	private int length = 0;

	public DoubleLinkedList() {
		super();
		headNode = new Node<T>();
		endNode = new Node<T>();
		headNode.pre = endNode;
		headNode.next = null;
		endNode.pre = null;
		endNode.next = headNode;
	}

	
	public int getLength() {
		return length;
	}


	/**
	 * list init through strings
	 * 
	 * @param strings
	 */
	public void init(T[] t) {

		length = t.length;
		for (int i = 0; i < t.length; i++) {
			Node<T> newNode = new Node<T>(t[i]);
			if (headNode.next == null) {// first insert
				headNode.next = newNode;
				newNode.pre = headNode;
				endNode = newNode;
				endNode.next = headNode;
				headNode.pre = endNode;
			} else {
				endNode.next = newNode;
				newNode.pre = endNode;
				endNode = newNode;
				endNode.next = headNode;
				headNode.pre = endNode;
			}
		}
	}

	public void clear() {
		
		for (Node<T> x = headNode; x != null;) {
			Node<T> next = x.next;
			x.data = null;
			x.next = null;
			x.pre = null;
			x = next;
		}
		headNode = endNode = null;
		length = 0;
	}

	/**
	 * return list length
	 * 
	 * @return
	 */
	public int listLength() {

		int length = 0;
		Node<T> node = headNode.next;
		if (node != null) {
			while (node.data != null) {

				length++;
				node = node.next;
			}
		}
		return length;
	}

	/**
	 * print list
	 */
	public void print() {

		Node<T> node = headNode.next;
		if (node != null) {
			while (node.data != null) {
				System.out.print(node.data + " ");
				node = node.next;
			}
		}
		System.out.println();
	}

	/**
	 * return Node by index
	 * 
	 * @param index
	 * @return
	 */
	public T get(int index) {

		Node<T> node = headNode.next;
		for (int j = 0; j < index; j++)
			node = node.next;
		return node.data;

	}

	public Node<T> getNode(int index) {

		Node<T> node = headNode.next;
		for (int j = 0; j < index; j++)
			node = node.next;
		return node;

	}

	/**
	 * add Node before a old Node
	 * 
	 * @param newNode
	 * @param node
	 */
	public void addBefore(Node<T> newNode, Node<T> node) {

		newNode.next = node;
		newNode.pre = node.pre;
		newNode.next.pre = newNode;
		newNode.pre.next = newNode;
		length++;
	}

	/**
	 * add Node after a old Node
	 * 
	 * @param newNode
	 * @param node
	 */
	public void addAfter(Node<T> newNode, Node<T> node) {

		newNode.pre = node;
		newNode.next = node.next;
		newNode.next.pre = newNode;
		newNode.pre.next = newNode;
		length++;
	}

	/**
	 * add Node by index
	 * 
	 * @param data
	 * @param index
	 */
	public void add(T data, int index) {
		
		if (index <= listLength()) {
			addBefore(new Node<T>(data), getNode(index));
		} else {
			System.out.println("out of range");
		}
	}

	/**
	 * remove a Node
	 * 
	 * @param node
	 */
	private void removeNode(Node<T> node) {

		node.pre.next = node.next;
		node.next.pre = node.pre;
		node.pre = null;
		node.next = null;
		length--;
	}

	/**
	 * remove Node from index
	 * 
	 * @param index
	 */
	public void remove(int index) {
		if (index >= listLength()) {
			System.out.println("out of range");
		}
		removeNode(getNode(index));

	}

	public void selectSort(int[] args) {// select

		// print(args);
		for (int i = 0; i < args.length - 1; i++) {
			int temp = 0;
			int index = i;// index of mix num
			for (int j = i + 1; j < args.length; j++) {
				if (args[j] < args[index]) {
					index = j;
				}
			}
			temp = args[index];
			args[index] = args[i];
			args[i] = temp;
		}
		// print(args);
	}

}
